// step 1# 开辟dp数组并初始化为0
int *initDP(int n) {
    int *dp = (int *)malloc(sizeof(int) * (n + 1));
    int i;
    for(i = 0; i <= n; ++i)
        dp[i] = 0;
    return dp;
}

// step 2# 主函数，计算n个节点的不同二叉搜索树数量
int numTrees(int n){
    // step 2.1# 初始化dp数组
    int *dp = initDP(n);

    // step 2.2# 设定基本情况：空树只有1种结构
    dp[0] = 1;

    int i, j;
    // step 2.3# 遍历每个节点数量，从1到n
    for(i = 1; i <= n; ++i) {
        // step 2.3.1# 枚举当前以每个节点为根的情况
        for(j = 1; j <= i; ++j) {
            // step 2.3.2# 应用递推公式：
            // 以j为根的树 = 左子树节点数(j-1)的种类数 × 右子树节点数(i-j)的种类数
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }

    // step 2.4# 返回n个节点对应的结果
    return dp[n];
}
